More Fun with Primes

In the first essay, Fun with Primes, two prime number sieves, one attributed to Eratosthenes and one that was a geometric, or visual, interpretation of such were examined. In this piece, we will study a different type of sieve. This sieve takes a different approach, one dealing more with parity, in generating the prime numbers.

Sieve of Sundaram

S. P. Sundaram was a student of mathematics from Sathyamangalam, East India in the early twentieth century. He discovered this sieve, which eliminates all composite numbers, from a list of natural values ranging from 1 to any n. His method is based upon the idea of parity, which is to say if a specific number is either odd or even. As can be readily discovered, consider what happens when you multiply values of the same or different parity:

An even number x another even number yields an even number

An even number x an odd number yields an even number 

An odd number x another odd number yields an odd number

We know that all even numbers with the exception of the number 2 are composite, as they are multiples of 2, so, we are really interested in what products will yield an odd number. From our examination above, it is important to know that in order to get an odd product, you must have two odd factors. We can call these odd factors (2i + 1) and (2j + 1), and their product (2n + 1).

(2i + 1)(2j + 1) = (2n + 1)

By expanding the right hand side of this equation, we have:

4ij + 2i + 2j + 1 = 2n + 1

Finally, we can simplify by subtracting 1 and dividing by 2 on both sides:

2ij + i + j = n

What this amounts to is if a value, n, can be expressed as 2ij + i + j (where i and j are natural numbers), then it can be doubled, and 1 added to form a composite number. Removing all such values for n eliminates all composite-producing values and leaves only prime-generating natural numbers.

So let’s look at a concrete example of how this works. Let’s say we want to develop a list of all prime values which are less than 100. We will need to determine (and eliminate!) all values for n which are less than 50 (because we will double n, and add 1 to achieve our list of primes).

These values for n which are composite-producing can be found by hand, or more expediently, by software. Below, you will see a table generated in Excel which calculates these values. The row headers are values for i, and the column headers are values for j. Note that only j values which are greater than or equal to i are utilized, as we do not need to do the same calculation for a mere permutation of i and j.

Composite-Generating Values for n

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
1	4	7	10	13	16	19	22	25	28	31	34	37	40	43	46	49
2		12	17	22	27	32	37	42	47	52	57	62	67	72	77	82
3			24	31	38	45	52	59	66	73	80	87	94	101	108	115
4				40	49	58	67	76	85	94	103	112	121	130	139	148
5					60	71	82	93	104	115	126	137	148	159	170	181
6						84	97	110	123	136	149	162	175	188	201	214

Notice that we don’t really need rows 5 and 6 as they do not contain any values less than or equal to 50.

1	11	21	31	41
2	12	22	32	42
3	13	23	33	43
4	14	24	34	44
5	15	25	35	45
6	16	26	36	46
7	17	27	37	47
8	18	28	38	48
9	19	29	39	49
10	20	30	40	50

Now we want to take a list of all natural numbers from 1 to 50 (remember this is half of the maximum upper bound that we previously determined), and eliminate all values that are found in the table. The table at right shows the list of these natural numbers, and the values from the table above are indicated by a strikethrough:

What remains looks like this:

1	11	21		41
2
3		23	33
	14			44
5	15		35
6		26	36
8	18			48
9		29	39
	20	30		50

3	23	43		83
5
7		47	67
	29			89
11	31		71
13		53	73
17	37			97
19		59	79
	41	61		101

What we have done thus far is to eliminate (or sieve out) all values for n that will generate composite numbers. Those values which remain will generate prime values when we double them, and add 1. The result of this simple calculation is shown in the table at right.

And so we see that this relatively recent discovery is yet another simple algorithm for determining the prime numbers.

Sources:

http://plus.maths.org/content/sundarams-sieve

http://luckytoilet.wordpress.com/2010/04/18/the-sieve-of-sundaram/

http://en.wikipedia.org/wiki/Sieve_of_Sundaram

http://pballew.blogspot.com/2010/03/different-prime-sieve.html